import matplotlib.pyplot as plt

def liang_barsky_clip(line, rect):
    x0, y0, x1, y1 = line
    xmin, ymin, xmax, ymax = rect
    
    dx = x1 - x0
    dy = y1 - y0
    p = [-dx, dx, -dy, dy]
    q = [x0 - xmin, xmax - x0, y0 - ymin, ymax - y0]
    
    u1, u2 = 0.0, 1.0
    
    for i in range(4):
        if p[i] == 0:
            if q[i] < 0:
                return None  # Line is parallel and outside the boundary
        else:
            u = q[i] / p[i]
            if p[i] < 0:
                u1 = max(u1, u)  # For entering points
            else:
                u2 = min(u2, u)  # For leaving points
    
    if u1 > u2:
        return None  # No visible part of the line is inside the rectangle

    clipped_x0, clipped_y0 = x0 + u1 * dx, y0 + u1 * dy
    clipped_x1, clipped_y1 = x0 + u2 * dx, y0 + u2 * dy

    return (clipped_x0, clipped_y0, clipped_x1, clipped_y1)

# 题给数据
line = (10, 45, 70, 75)
clip_rect = (20, 20, 120, 70)
clipped_line = liang_barsky_clip(line, clip_rect)
print("Clipped Line:", clipped_line)

# 可视化
fig, ax = plt.subplots()
ax.set_xlim(0, 130)
ax.set_ylim(0, 80)

# 绘制裁剪窗口
rect_x = [clip_rect[0], clip_rect[2], clip_rect[2], clip_rect[0], clip_rect[0]]
rect_y = [clip_rect[1], clip_rect[1], clip_rect[3], clip_rect[3], clip_rect[1]]
ax.plot(rect_x, rect_y, 'k-', label='Clipping Window')

# 绘制原始线段
ax.plot([line[0], line[2]], [line[1], line[3]], 'r--', label='Original Line')

# 绘制裁剪后的线段
if clipped_line:
    ax.plot([clipped_line[0], clipped_line[2]], [clipped_line[1], clipped_line[3]], 'g-', label='Clipped Line')

# 添加图例
ax.legend()
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Liang-Barsky Line Clipping')
plt.grid(True)
plt.show()